SP17247 Digit Sum

每个数的数字和的和其实就是所有数字与它出现次数的积的和。

那么对于 090-9 ,依次像 P2602 [ZJOI2010]数字计数 统计出现次数就可以了。

具体做法也很简单,记录前 pospos 位某个数字出现次数 sumsum,记忆化搜索即可通过。

最后附上双倍经验:P4999 烦人的数学作业

#include <cstdio>
#include <cstring>
#define int long long

const int MAXN = 15;
int a[ MAXN + 5 ] , len , dp[ MAXN + 5 ][ MAXN + 5 ];

int dfs( int pos , int lead , int limit , int sum , int digt ) {
	if( pos == len + 1 ) return sum;
	if( ~dp[ pos ][ sum ] && !lead && !limit ) return dp[ pos ][ sum ];
    
	int Ans = 0 , Mbit = limit ? a[ len - pos + 1 ] : 9;
	for( int i = 0 ; i <= Mbit ; i ++ ) {
		if( lead && i == 0 ) Ans += dfs( pos + 1 , 1 , limit & ( i == Mbit ) , sum , digt );
        else                 Ans += dfs( pos + 1 , 0 , limit & ( i == Mbit ) , sum + ( i == digt ) , digt );
	}
	if( !lead && !limit ) dp[ pos ][ sum ] = Ans;
	return Ans;
}
int Solve( int digt , int x ) {
    if( x < 0 ) return 0;
	len = 0; for( ; x ; x /= 10 ) a[ ++ len ] = x % 10;
	memset( dp , -1 , sizeof( dp ) );
	return dfs( 1 , 1 , 1 , 0 , digt );
}

int t , l , r , Ans;
signed main( ) {
    scanf("%lld",&t);
    while( t -- ) {
        scanf("%lld %lld",&l,&r);
        Ans = 0;
        for( int i = 0 ; i <= 9 ; i ++ ) Ans += i * ( Solve( i , r ) - Solve( i , l - 1 ) );
        printf("%lld\n", Ans );
    }
	return 0;
}